package com.atguigu.interview.base;

import cn.hutool.core.date.DateUtil;
import cn.hutool.core.date.TimeInterval;

/**
 * @author Jungle
 * @create 2022-09-06 12:13
 * 编程题:有n步台阶，一次只能上1步或2步，共有多少种走法?
 *
 *
 * 小结
 * ·方法调用自身称为递归，利用变量的原值推出新值称为迭代。·递归
 * ·优点:大问题转化为小问题，可以减少代码量，同时代码精简，可读性好;·缺点:递归调用浪费了空间，而且递归太深容易造成堆栈的溢出。
 * ·迭代
 * ·优点:代码运行效率好，因为时间只因循环次数增加而增加，而且没有额外的空间开销;
 * ·缺点:代码不如递归简洁，可读性好
 *
 * 1.递归
 * 2.循环迭代
 */
public class LadderDemo {
    /**
     * 1、实现f(n) :求n步台阶一共有多少种走法
     */
    public static void main(String[] args) {
        TimeInterval timer = DateUtil.timer();
        timer.start("m1");
        long n = f(40);

        timer.start("m2");
        long n2 = loop(40);
        System.out.println(n + "\t耗时\t" + timer.interval("m1"));
        System.out.println(n2 + "\t耗时\t" + timer.interval("m2"));

    }

    /**
     * 1、方法1、递归
     */
    private static long f(long n) {
        if (n >= 1) {
            if (n == 1 || n == 2) {
                return n;
            }
            return f(n - 2) + f(n - 1);
        }
        return 0;
    }

    /**
     * 1、方法2、循环迭代
     */
    private static long loop(long n) {
        if (n >= 1) {
            if (n == 1 || n == 2) {
                return n;
            }
            //初始化为走到第二级台阶的走法
            int one = 2;
            //初始化为走到第一级台阶的走法
            int two = 1;
            int sum = 0;
            for (int i = 3; i <= n; i++) {
                sum = two + one;
                two = one;
                one = sum;
            }
            return sum;
        }
        return 0;
    }
}
